package _02_链表;

public class _83_删除排序链表中的重复元素 {

    // 递归
    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null) return null;
        // 已经剔除重复元素，设置到前一个节点的下一个节点
        ListNode subNode = deleteDuplicates1(head.next);
        // 判断上一个节点和当前节点值是否相同
        if (subNode != null && head.val == subNode.val) {
            // 相同删除当前节点
            head.next = subNode.next;
        } else {
            head.next = subNode;
        }
        return head;
    }

    public ListNode deleteDuplicates2(ListNode head) {
        // 1.递归出口 链表为空者返回head，或者链表只剩下一个元素。则肯定无重复直接返回
        if (head == null || head.next == null) return head;

        // 2.判断当前函数逇作用是什么，返回一个已经除去重复的元素，链表已经改动
        head.next = deleteDuplicates2(head.next);

        // 3.每一步需要做什么，head.next已经指向了一个除去重复的链表
        if (head.val == head.next.val) head = head.next;
        return head;
    }

    // 非递归
    public ListNode deleteDuplicates(ListNode head) {
        ListNode newHead = head;
        ListNode prevNode = newHead;
        while ((head != null) && (newHead = newHead.next) != null) {
            if (prevNode.val == newHead.val) {
                // 去除后面元素
                prevNode.next = newHead.next;
            } else {
                prevNode = newHead;
            }
        }
        return head;
    }
}
